package com.canopys.study.open.test.algorithm.dynamic;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 10:53 2020/12/6
 * @Modified By:
 */
public class ZeroOne {

    // n 决策的低几个物品， cw 背包中的重量
    // f(n, cw) = true 推导出
    // f(n+1, cw) = true , f(n+1, cw+w[n+1]) = true
    // 实现就是遍历 n(阶段) , w(状态)
    public static void knapsack(int[] weight, int w) {
        // w + 1 为 0 + w
        boolean[][] states = new boolean[weight.length][w + 1]; // 默认值 false

        // 初始化
        states[0][0] = true;
        states[0][weight[0]] = true;

        // i 表示阶段  w+1 表示状态
        for (int i = 1; i < weight.length; i++) {
            // j 表示重量，重量有w+1个状态
            for (int j = 0; j <= w; j++) {
                // 不装入n（阶段），n的重量（状态）为n-1的重量（状态）
                if (states[i - 1][j]) {
                    states[i][j] = true;
                }
            }

            // 装入n（阶段）， n的重量（状态）为n-1的重量 + n本身的重量 （状态）
            for (int j = 0; j <= w - weight[i]; j++) {
                if (states[i - 1][j]) {
                    states[i][j + weight[i]] = true;
                }
            }
        }

        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < w + 1; j++) {
                if (states[i][j]) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }

        for (int j = w; j >= 0; j--) {
            for (int i = weight.length - 1; i >= 0; i--) {
                if (states[i][j]) {
                    System.out.println(j);
                    return;
                }
            }
        }
    }

    public static void knapsackV(int weight[], int v[], int w) {
        int[][] states = new int[weight.length][w + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j <= w; j++) {
                states[i][j] = -1;
            }
        }

        states[0][0] = 0;
        states[0][weight[0]] = v[0];

        for (int i = 1; i < weight.length; i++) {
            for (int j = 0; j <= w; j++) {
                if (states[i - 1][j] >= 0) {
                    if (states[i - 1][j] > states[i][j]) {
                        states[i][j] = states[i - 1][j];
                    }
                }
                /*if (states[i - 1][j] > states[i][j]) {
                    states[i][j] = states[i - 1][j];
                }*/
            }

            for (int j = 0; j <= w - weight[i]; j++) {
                if (states[i - 1][j] >= 0) {
                    if (states[i - 1][j + weight[i]] + v[i] > states[i][j + weight[i]]) {
                        states[i][j + weight[i]] = states[i - 1][j] + v[i];
                    }
                }
            }
        }

        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < w + 1; j++) {
                System.out.print(states[i][j] + " ");
            }
            System.out.println();
        }


    }

    public static int candy(int[] ratings) {
        if (null == ratings || ratings.length == 0) {
            return 0;
        }

        if (ratings.length == 1) {
            return 1;
        }

        int[] left = new int[ratings.length];
        left[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                ratings[i] = ratings[i - 1] + 1;
            } else {
                ratings[i] = 1;
            }
        }

        int sum = Math.max(left[ratings.length - 1], 1);
        int right = 1;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i + 1] < ratings[i]) {
                right++;
            } else {
                right = 1;
            }
            sum = sum + Math.max(left[i], right);
        }

        return sum;


    }


    public static void main(String[] args) {
        /*int[] w = new int[] {2, 2, 4, 6, 3};
        int[] v = new int[] {3, 4, 8, 9, 6};
        knapsack(w, 9);
        System.out.println();
        System.out.println();
        System.out.println();
        knapsackV(w, v, 9);Math.min()
        String s =;
        s.charAt()
                s.indexOf()

        Map<String, Integer> map = new HashMap<>();

        map.forEach((k, l) -> { if( ) };

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() != -1) {}
        }*/
        int[] w = new int[] {1,0,2};
        candy(w);
    }
}
